package leetcode.heap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Lc347 {

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);

        }
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            pq.offer(entry.getKey());
            if (pq.size() > k)
                pq.poll();
        }

        int[] ans = new int[k];
        while (!pq.isEmpty()) {
            ans[--k] = pq.poll();
        }
        return ans;
    }


}
